package week7;

import java.util.ArrayList;
import java.util.List;

/**
 *
 * 22. 括号生成
 * https://leetcode-cn.com/problems/generate-parentheses/
 *
 *
 * 执行结果：  通过  显示详情
 *
 * 添加备注
 * 执行用时：1 ms, 在所有 Java 提交中击败了79.52% 的用户
 * 内存消耗：38.3 MB, 在所有 Java 提交中击败了90.37% 的用户
 * 通过测试用例：8 / 8
 * 炫耀一下:
 *
 *
 */
public class Week7GenerateParentheses {

    public List<String> generateParenthesis(int n) {
        List<String> list = new ArrayList<String>();

        if(n != 0) {
            dfs("", 0, 0, n, list);
        }

        return list;
    }

    /**
     * 递归生成括号
     *
     * @param current 当前字符串
     * @param left 做括号数量
     * @param right 右括号数量
     * @param n 括号总量
     * @param list 所有括号列表
     */
    private void dfs(String current, int left, int right, int n, List<String> list) {
        if(left == n && right == n) {
            // 终止
            list.add(current);
            return;
        }

        if(left < right) {
            // 剪枝 左侧变少不符合
            return;
        }

        if(left < n) {
            // 添加左括号
            dfs(current + "(", left + 1, right, n, list);
        }

        if(right < n) {
            // 添加右括号
            dfs(current + ")", left, right + 1, n, list);
        }


    }
}
